The field of the present invention relates to signal processing and, more particularly, to a method and apparatus for determining the occurrence of transitions in a binary encoded input signal such as a scanned bar code label.
Signals having transitions between binary levels are generated from many different devices. For example, optical scanners have been used to read encoded information on bar code labels and generate analog signals comprised of substantially binary levels. Bar codes typically consist of a series of parallel light and dark rectangular areas of varying widths. The light areas are often referred to as xe2x80x9cspacesxe2x80x9d and the dark areas as xe2x80x9cbarsxe2x80x9d. Different widths of bars and spaces are selected in order to define different characters of a bar code.
A bar code label is typically read by a scanner which detects reflected and/or diffracted light from the bars and spaces comprising the characters. One common method of illuminating the bar code label is by use of a scanning laser beam, in which case the reflected light is detected by an optical detector. The detector generates an electrical signal having an amplitude determined by the intensity of the collected light. Another method for illuminating the bar code label is by use of a uniform light source with an array of optical detectors connected to an analog shift register (commonly called a charge-coupled device or CCD). In such a technique, as with a scanning laser, an electrical signal is generated having an amplitude determined by the intensity of the collected light. In either the scanning laser or CCD technique, the amplitude of the electrical signal has one level for dark bars and a second level for light spaces. The precise amplitudes of the two levels, however, are not known prior to scanning. As a label is scanned, positive-going transitions and negative-going transitions in the electrical signal occur, signifying transitions between-bars and spaces. The transitions in the electrical signal are not perfectly sharp but may be gradual or noisy, thus making it difficult to determine the precise instant at which the transition has occurred. Inaccuracies in determining transition points may cause a bar code label to be misread.
Several techniques in signal processing have been developed for the purpose of determining transitions with greater accuracy. One such technique involves the detection of zero crossings of the second time derivative of the input signal. The benefits of using a second derivative signal processing method for bar code readers are well known and are set forth, for example, in U.S. Pat. No. 4,000,397 entitled xe2x80x9cSignal Processor Method and Apparatusxe2x80x9d (issued Dec. 28, 1976).
Derivatives of the input signal in scanning systems are typically generated in an analog fashion by RC circuits. Differentiation circuits for obtaining analog derivatives of the input signal are well known by those skilled in the art and primarily comprise one or more operational amplifiers along with resistors and capacitors. Such differentiation circuits implement for the first derivative a transfer function having a zero at the origin and a single pole chosen beyond the highest frequency of interest. For the second derivative, such circuits implement a transfer function having two zeros at the origin and two poles chosen beyond the highest frequency of interest.
As the demand for accuracy and versatility in scanners continues to grow, conventional implementation methods of the second derivative technique may experience limitations. One such limitation is the ability to reject noise in the high frequency regions. As system performance is strongly affected by noise present in such regions, conventional implementations usually require the addition of a relatively complex low pass filter in the signal processing chain. Further, susceptibility to noise interference is affected by the fact that, while noise power tends to increase at higher frequencies, input signal power tends to roll off at such frequencies. The differentiation operation used in the conventional method to obtain the first or second derivative signals provides little or no attenuation outside the bandwidth of interest (i.e., the frequency band that contains most of the energy resulting from the light reflected from the symbol) and is therefore susceptible to high frequency noise.
A second limitation, related to the first, is that the conventional differentiator circuit: does not exhibit flat group delay, or linear phase response, over the frequency band of interest. Group delay may be defined as the delay time of a circuit or system at various frequency values. A system exhibiting xe2x80x9cflatxe2x80x9d group delay has a relatively uniform delay time over the bandwidth of interest. Such a system is therefore said to have linear phase response. A system that does not exhibit flat group delay has relatively nonuniform or varying delay times dependent upon input signal frequency. Such a system is therefore said to have nonlinear phase response. Bar code scanner systems utilizing conventional differentiator circuits may, as a result of not having flat group delay, distort pulse shapes leading to errors in detecting pulse widths.
This type of distortion may be illustrated with reference to FIG. 1. FIG. 1 is a graph comparing the output O1 of a low pass filter having nonconstant group delay compared to the output O2 of an ideal filter having linear phase response or constant group delay in response to an input pulse P. The output O1 of the filter with nonconstant group delay exhibits asymmetry and over/undershoot resulting from a nonlinear phase characteristic, possibly leading to incorrect or unsuccessful decoding of the symbol. To avoid distorting the shapes of pulses that occur in a bar code signal processing system, it is thus highly desirable that the entire system exhibit linear phase response or, equivalently, constant group delay.
Another related problem may occur while attempting to detect the zero crossings of the second derivative signal. Typically, the first derivative of the input signal is looked to in order to determine the time periods during which a valid zero crossing of the second derivative signal may occur. Zero crossings of the second derivative signal are considered valid if occurring during a portion of the first derivative signal peak. However, a common problem in conventional systems is that the first and second derivative signals are not properly aligned in time because of temperature and frequency dependent delays in the first and second differentiator circuitry. Significant misalignment of the first and second derivative signals may occur causing missed zero crossings or detection of false zero crossings of the second derivative signal.
Further problems have been created by increasing demand for greater depth of field in handheld scanners. Greater depth of field requirements result in a larger range of signal amplitudes leading to the potential for clipping of the input signals or derivative signals. Clipping typically occurs when a signal is limited by a positive or negative voltage supply level. Although enlarging the supply voltage may increase the dynamic range of operation and thereby minimize clipping, there is also a benefit in keeping power and voltage levels low to accommodate smaller, lighter and cheaper handheld scanners. Moreover, greater depth of field in scanners further accentuates the noise problems mentioned above as higher frequencies are generated as a result of using smaller labels and reading labels at longer distances. Reading labels at longer distances also reduces the strength of the input signal thus increasing the need to reduce the effects of noise.
The present invention provides a method and apparatus for detecting the transitions between binary levels of an input signal. The preferred method of the invention is based on approximating the derivative operation with the mathematical operation:
F(t)xe2x88x92F(txe2x88x92D)
where F(t) is the electrical signal that represents the reflected light from the symbol, t is the time variable and D is a fixed time delay. The derivative of the signal is in effect approximated by the slope of a straight line between two points on the waveform separated by the delay time D.
In one embodiment the delayed version of the signal is obtained from a circuit element known as a delay line. A primary benefit of this technique is that delay lines, by definition, have constant group delay (and therefore linear phase) over the entire range of operation. The frequency response of the delay line differentiator is a periodic type response (often called a xe2x80x9ccombxe2x80x9d filter). The first null in the response is given by the formula f(min)=1/D where D is the delay time of the delay element and f(min) is in Hertz. If the delay time is chosen so that the frequency response has begun to decrease immediately beyond the frequencies of interest, the system has the advantageous property of reducing the amplitude of high frequency noise components while performing the differentiating function. In addition, as mentioned above, such filtering is done with completely linear phase.
The above concepts are further extended to obtain a second derivative signal using two delay elements. The signals entering the circuit, exiting the first delay element and exiting the second delay element are referred to as A, B and C respectively. The numerical approximation to the first derivative is the difference between two adjacent samples or Axe2x88x92B. Another approximate first derivative is calculated by Bxe2x88x92C. An approximation of the second derivative is calculated from the difference between the two first derivatives, or:
(Axe2x88x92B)xe2x88x92(Bxe2x88x92C)=A+Cxe2x88x922B
A summing amplifier may be used to perform the arithmetic operations to produce an approximation to the second derivative. The frequency response of this delay line second derivative circuit is also of a comb filter variety and has the advantageous property of reducing the amplitude of high frequency noise components while performing the differentiating function.
Once the second derivative signal is obtained in the above fashion, transitions between spaces and bars may be determined by locating the zero crossings of the second derivative signal in a manner such as that used in U.S. Pat. No. 4,000,397, incorporated herein by reference, or by various other techniques further explained herein. An important benefit of delay line differentiation is that, by virtue of the fixed delay intervals, the first and second derivatives are properly aligned in time such that the peak amplitude of the first derivative may be used to assist detection of the second derivative zero crossings. A further advantage of the above technique is the ability to maintain a suitable dynamic range of operation while minimizing sensitivity to clipping of signal amplitudes. Dynamic range is improved because the second derivative signal is derived independently from the first derivative signal; thus, clipping of the first derivative signal will not affect the precision of the second derivative signal.
An embodiment may also include an additional low pass filter in the system for attenuating any undesired high frequency noise beyond the bandwidth of interest. Such a filter need not have linear phase response beyond the bandwidth of interest and may therefore be a simple, well known filter type (such as a four-pole transitional Gaussian 12-dB) without degrading the shape of the signal pulses and providing, in combination with the delay line differentiator, superior overall system frequency response and group delay characteristics.
In another embodiment of the present invention the delay elements may be implemented as active all pass filters and therefore have the advantage of being easily adjusted to compensate for phase nonlinearities that arise in other parts of the system. In yet another embodiment, the delay periods may be adjustable so as to enable accurate scanning over a greater depth of field.
A zero crossing detector is provided in one embodiment whereby a valid zero crossing is determined by detecting a preceding signal peak and a subsequent, opposite-polarity signal peak of a minimum amplitude a predefined distance surrounding the zero crossing. In a particular version of this embodiment, the second derivative signal is applied to a series of two delay elements. The output of the first delay element is tested for zero crossings, while the input to the delay element series and the output of the delay element series are tested for positive and negative signal peaks meeting the specified criteria.
In several variations of the above embodiment, means are provided to compensate for intersymbol interference. In one variation, the peak signal values are measured and used to derive an estimate of the slope of the second derivative signal at the zero crossing. The calculated slope is applied to a look-up table to obtain a zero-crossing correction factor. In another variation, the peak signal values are compared. The difference value is applied to a look-up table to obtain a zero-crossing correction factor. In another variation, relative widths of the positive and negative signal pulses are compared. The difference value may be applied to a look-up table to obtain a zero-crossing correction factor, or may be halved and used as an estimate of zero crossing displacement.
The foregoing and other objects, features, and advantages of the invention will become apparent from the following more detailed description set forth in conjunction with the accompanying drawings.